package weekMatch.two_103;

import sun.security.provider.Sun;

import java.util.Arrays;
import java.util.Comparator;

public class LeeCode_04_2 {
    public static void main(String[] args) {

    }
    public long countOperationsToEmptyArray(int[] nums) {
        int n = nums.length;
        Integer[] id = new Integer[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
        Arrays.sort(id, Comparator.comparingInt(i -> nums[i]));

        long ans = n;
        BIT t = new BIT(n + 1);
        int pre = 1;
        for (int k = 0; k < n; ++k) {
            int i = id[k] + 1;
            if (i >= pre){
                ans += i - pre - t.query(pre, i);
            }else {
                ans += n - pre + i - k + t.query(i, pre - 1);
            }
            t.inc(i);
            pre = i;
        }
        return ans;
    }
}
class BIT{
    private final int[] tree;
    public BIT(int n){
        tree = new int[n];
    }
    public void inc(int i){
        while (i < tree.length){
            ++tree[i];
            i += i & -i;
        }
    }

    public int sum(int x){
        int res = 0;
        while (x > 0){
            res += tree[x];
            x &= x - 1;
        }
        return res;
    }

    public int query(int left, int right){
        return sum(right) - sum(left - 1);
    }
}
